package DataStructure.LinkedLearning.SingleLinkedList.JudgeTheRing;

/**
 *  学习 利用快慢指针判断单链表内是否存在环
 */
public class Demo {
    public static void main(String[] args) {
        Node node7 = new Node(7, null);
        Node node6 = new Node(6, node7);
        Node node5 = new Node(5, node6);
        Node node4 = new Node(4, node5);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node node1 = new Node(1, node2);

        // 加环
        //node7.next = node5;

        // 判断该单链表是否有环存在
        boolean flag = judge(node1);
        if(flag) {
            System.out.println("有环");
        } else {
            System.out.println("没有环");
        }
    }

    public static boolean judge(Node head) {
        // 设置快指针和慢指针
        Node fast = head;
        Node slow = head;
        // 两个条件不能省略
        while(fast.next != null && fast.next.next != null) {
            // 快指针一次走两格
            fast = fast.next.next;
            // 慢指针一次走一格
            slow = slow.next;
            // 当相遇时跳出循环
            if(fast == slow) {
                break;
            }
        }
        // 如果不是因为快指针走到末尾而跳出，则表示快慢指针相遇
        // 证明有环
        if(fast.next != null && fast.next.next != null) {
            return true;
        } else {
            return false;
        }
    }
}
